package com.xixi.basicAlgroithms;

import java.util.ArrayList;
import java.util.List;

/**
 * 组合：如果要想在 n 个物品中，选择 k 个物品出来，选择的顺序无所谓，那么选择的方式总共有这么多
 * @author vincentML
 * @date 2022-04-13  13:49
 */

public class Combination {


    public List<List<Integer>> result = new ArrayList<>();
    public static void main(String[] args) {

        Combination combination = new Combination();
        System.out.println( combination.combination(new int[]{1,2,3,4,5}, 3));
        System.out.println( combination.result.size());


    }


    public List<List<Integer>> combination(int[] nums, int k){

        //nums中取k个数字，有多少总组合

        backTracking(nums, nums.length, k, 0, new ArrayList<>());

        return result;
    }

    /*
     * @Desc:
     * @Author vincentML
     * @Date: 2022/4/13 13:54
     * @param nums  数字集合
     * @param nLength nums的长度
     * @param k 取多少个数
    */
    public void backTracking(int[] nums, int nLength, int k, int index, List<Integer> path){
        if(path.size() == k){ //取够了
            result.add(new ArrayList<>(path)); //快照
            return;
        }

        //剪枝，如果接下来不够取了就不用递归了
        // 还需要取的数字，  k - path.size()

        //还有这么多数字可以选择，nLength - index

        if( (nLength - index) < (k-path.size())){
            return;
        }

        path.add(nums[index]); //路径里加上当前值
        backTracking(nums, nLength, k, index + 1, path);
        path.remove(path.size() -1); //路径里没有当前值
        backTracking(nums, nLength, k, index + 1,path);




    }

}
